The present invention relates generally to techniques for arbitrating access to a shared resource. One particular example is a device having multiple inputs and outputs for routing message traffic in a communications network. More particularly, the invention relates to a method, and apparatus for implementing that method, to bias the arbitration between two or more inputs of the device that are contending for data communication access to the same output of the device.
As multiprocessing environments grow, the ability to provide data communication between the individual system elements (i.e., processors and peripheral equipment) of the system requires careful thought so as not to inadvertently give a system element unfair access to a communications path or some other shared resource (e.g., a multiple-user bus system) while, at the same time, limiting such access to other system elements.
Many of today""s data communication networking configurations will use various devices (typically, xe2x80x9croutersxe2x80x9d) to direct or otherwise route message traffic from one communications link to one of a number of other communications links. However, message traffic can be received at two or more inputs of the device at substantially the same time bound for the same output, raising the issue of which of the two will be allowed to proceed before the other, i.e., who goes first. Access to the output requires some form of arbitration between the two contending inputs. Smaller systems (i.e., those with a small number of system elements needing to communicate with one another) may use such classic arbitration techniques as assigning fixed priorities to the inputs or xe2x80x9cround-robinxe2x80x9d processing. In the former, each port input is provided a predetermined priority to form a hierarchical arbitration scheme. Inputs with higher priority will be given access to an output over inputs with lower pre-assigned priorities seeking access to that same output. The round-robin technique involves assigning priorities according to a predetermined order among the inputs. As message traffic is received, the priorities change so that the last input granted access to a particular output is then given the lowest priority, and the next input in order now has the highest priority; the remaining inputs will have their priorities similarly changed according to the predetermined order.
Similar techniques may be used in other shared resource environments such as, for example, multiple-user bus systems, to allocate access to the bus between connected controllers.
As computing systems become more complex, so that the number of elements (processors and peripheral units) increase, it would not be unusual for an input of a routing device to be required to route message traffic from several elements. Further, routing devices are sometimes cascaded to form, for example, tree-like network configurations, increasing the number of system elements that may need to route message traffic through an input of a routing device. Using pre-assigned priorities, round-robin processing, or other similar techniques can unfairly allocate the services of a routing device""s input to some of the system""s elements at the expense of other elements that use another input of that routing device. For example, a routing device may receive at one input message traffic from only one system element, while another input of that same routing device is required to service several elements. Using any of the above techniques will operate to give more of the routing device""s attention to the one element, and less attention to each of the several elements using the second input. Thus, prior arbitration techniques can unfairly allocate more of the routing device""s services to the input having the lesser number of system elements using that routing device.
One solution to assuring fair allocation of services to device inputs is to use biased arbitration techniques. With biased arbitration, each input has a bias value that determines the percentage of time it will win arbitration.
Biased arbitration can be used either to assure fair access to all nodes, or to purposely give some paths higher priority than other paths. Biased arbitration can be used to help support quality of services (QOS) guarantees for real-time or constant bit rate traffic.
One biased arbitration system is described in U.S. Pat. No. 5,694,121, assigned to the assignee of the present application, which discloses an ALU arbitration technique. Each port has a bias value provided and has an associated accumulator. The port with the highest value in its accumulator wins arbitration. The winner then decrements its accumulator by sum of the bias values of all the losers, and each loser increments its accumulator by its own bias value. Another biased arbitration system is described in U.S. Pat. No. 5,710,549, which is also assigned to the assignee of the present application.
This ALU biasing scheme works well for routers with small numbers of ports. However, it does not scale well to larger routers because large adders and logic for pairwise comparisons of all accumulators are required to determine a current arbitration winner.
Accordingly, research continues to develop effective biased arbitration techniques of utility on complex systems.
According to one aspect of the present invention, requestors are assigned bias values which are encoded as binary bias vectors. The bias vectors are stored as columns in a matrix, with each column corresponding to a particular requester. During an arbitration the rows of the matrix are fetched; thus, the matrix is designated a transpose matrix. The rows are fetched in a way that gives the correct biasing and also gives the lowest possible latency.
According to another aspect of the invention, storage areas hold requester identifiers identifying unique requesters in a plurality of requesters. Storage areas are accessed at different frequencies. Requestors assigned a high bias priority have their requestor identifiers stored in one or more storage areas that are accessed at a higher frequency and requesters having a low bias priority have their requestor identifiers stored in one or more storage locations accessed at a lower frequency.
According to another aspect of the invention, the rows are fetched by a mapped counter output. The counter output is mapped so that rows having more significant bit positions of the binary bias vectors are fetched more frequently that less significant bit positions.
According to another aspect of the invention, bias vectors for requestors not having a request pending are masked during an arbitration.
According to another aspect of the invention, most significant rows having no active request are masked to avoid fetching the rows.
According to another aspect of the invention, a compression technique is utilized to reduce storage in the case where a transpose matrix stores a large number of xe2x80x9c0xe2x80x9ds.
Other features and advantages will be apparent in view of the following detailed description and appended drawings.